# https://leetcode-cn.com/problems/longest-increasing-subsequence/
# 300. 最长递增子序列
# 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
#
# 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
#
#
# 示例 1：
#
# 输入：nums = [10,9,2,5,3,7,101,18]
# 输出：4
# 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
# 示例 2：
#
# 输入：nums = [0,1,0,3,2,3]
# 输出：4
# 示例 3：
#
# 输入：nums = [7,7,7,7,7,7,7]
# 输出：1
#
#
# 提示：
#
# 1 <= nums.length <= 2500
# -104 <= nums[i] <= 104
#
#
# 进阶：
#
# 你可以设计时间复杂度为 O(n2) 的解决方案吗？
# 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

# dp[i]的值代表nums以nums[i]结尾的最长子序列长度。
#

from typing import List


class Solution:
    @staticmethod
    def print_series(_s: dict, i: int):
        if i in _s:
            mm = Solution.print_series(_s, _s[i])
            return mm + [i]
        else:
            return [i]

    def lengthOfLIS_series(self, nums: List[int]) -> int:
        """
        最长连续递增子序列, 序列必须前后相连
        :param nums:
        :return:
        """
        # 截止到i的最短有序子序列长度
        d = [1 for _ in range(len(nums))]
        # i最短子序列起始的id
        s = list(range(len(nums)))

        for i in range(len(nums)):
            if i == 0:
                continue
            if nums[i] > nums[i - 1]:
                d[i] = d[i - 1] + 1
                s[i] = s[i - 1]

        max_id, max_num = max(enumerate(d), key=lambda x: x[1])
        print('最大连续递增子序列:', nums[s[max_id]:(max_id + 1)])
        print('最大连续递增子序列长度: %d' % max_num)

        return max_num

    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        最长递增子序列   序列中的元素在nums中可以不连续
        :param nums:
        :return:
        """
        # 以nums[i]结尾的最短有序子序列长度
        d = [1 for _ in range(len(nums))]
        # 最短子序列的上一个id
        s = {}

        for i in range(len(nums)):
            if i == 0:
                continue

            ss = [(d[j] + 1, j) for j in range(0, i) if nums[i] > nums[j]]
            if len(ss) == 0:
                continue
            d_j, max_j = max(ss, key=lambda x: x[0])
            d[i] = d_j
            s[i] = max_j

        max_id, max_num = max(enumerate(d), key=lambda x: x[1])
        print('d', d)
        print(s, max_id)
        print('最大递增子序列', Solution.print_series(s, max_num))
        print('最大递增子序列长度: %d' % max_num)

        return max_num

    def lengthOfLIS2(self, nums: List[int]) -> int:
        """
        最长递增子序列优化   序列中的元素在nums中可以不连续
        ----
        时间复杂度O(N*log(N))
        参考: https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/

        在遍历查找d[i]的时候，原需要遍历j in range(0, i), 这里改用空间换时间:
        - 维护一个当前最大的序列长度变量, max_length
        - 维护一个tails表, tails[k]表示长度为k+1的所有序列中, 末尾值最小的值 --同样长度的序列, 末位置小的序列后续成长空间更大, 成长空间是大的的父集
        寻找d[i]的步骤:
        1)寻找: k = min{k | tails[k] > nums[i], i <= max_length}
        2)如果存在, 更新: tails[k] = nums[k]
        3)如果不存在, 更新:
                        max_length += 1
                        tails[max_length] = nums[i]
        分析:
        由于tails是一个严格递增数组, 因此第一步查找时可以使用二分查找
        :param nums:
        :return:
        """
        # 截止到i的最短有序子序列长度
        tails = [0 for _ in range(len(nums))]

        max_length = 0
        for i in range(len(nums)):
            k, e = 0, max_length
            while k < e:
                m = (k + e) // 2
                if tails[m] < nums[i]:
                    k = m + 1
                else:
                    e = m

            tails[k] = nums[i]
            if k == max_length:
                max_length += 1
        return max_length


# assert Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) == 4
# assert Solution().lengthOfLIS([0, 1, 0, 3, 2, 3]) == 4
# assert Solution().lengthOfLIS([7, 7, 7, 7, 7, 7, 7]) == 1

assert Solution().lengthOfLIS2([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert Solution().lengthOfLIS2([0, 1, 0, 3, 2, 3]) == 4
assert Solution().lengthOfLIS2([7, 7, 7, 7, 7, 7, 7]) == 1

# assert Solution().lengthOfLIS_series([10, 9, 2, 5, 3, 7, 101, 18]) == 3
# assert Solution().lengthOfLIS_series([0, 1, 0, 3, 2, 3]) == 4
# assert Solution().lengthOfLIS_series([7, 7, 7, 7, 7, 7, 7]) == 1
from sklearn.neighbors import KNeighborsRegressor